Local search algorithms applied to optimization problems often suffer fromgetting trapped in a local optimum. The common solution for this deficiency isto restart the algorithm when no progress is observed. Alternatively, one canstart multiple instances of a local search algorithm, and allocatecomputational resources (in particular, processing time) to the instancesdepending on their behavior. Hence, a multi-start strategy has to decide(dynamically) when to allocate additional resources to a particular instanceand when to start new instances. In this paper we propose multi-startstrategies motivated by works on multi-armed bandit problems and Lipschitzoptimization with an unknown constant. The strategies continuously estimate thepotential performance of each algorithm instance by supposing a convergencerate of the local search algorithm up to an unknown constant, and in everyphase allocate resources to those instances that could converge to the optimumfor a particular range of the constant. Asymptotic bounds are given on theperformance of the strategies. In particular, we prove that at most a quadraticincrease in the number of times the target function is evaluated is needed toachieve the performance of a local search algorithm started from the attractionregion of the optimum. Experiments are provided using SPSA (SimultaneousPerturbation Stochastic Approximation) and k-means as local search algorithms,and the results indicate that the proposed strategies work well in practice,and, in all cases studied, need only logarithmically more evaluations of thetarget function as opposed to the theoretically suggested quadratic increase.
展开▼
